﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0108_SetZeroes : IAlgorithm
    {
        // 73. 矩阵置零

        // 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

        // 提示：
        //  m == matrix.length
        //  n == matrix[0].length
        //  1 <= m, n <= 200
        //  -2^31 <= matrix[i][j] <= 2^31 - 1


        // 进阶：
        //  一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
        //  一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
        //  你能想出一个仅使用常量空间的解决方案吗？

        public void Test()
        {
            // 算法参数定义
            var matrix = new int[][] {
                new int[] { 0, 1, 2, 0 } ,
                new int[] { 3, 4, 5, 2 },
                new int[] { 0, 3, 1, 5 }
            };
            // 算法执行与打印
            SetZeroes(matrix);
            foreach (var item in matrix)
            {
                foreach (var iitem in item)
                {
                    Console.Write(iitem + " ");
                }
                Console.WriteLine();
            }
        }

        // 算法
        public void SetZeroes(int[][] matrix)
        {
            int m = matrix.Length, n = matrix[0].Length;
            bool flagCol0 = false;
            for (int i = 0; i < m; i++)
            {
                if (matrix[i][0] == 0) flagCol0 = true;
                for (int j = 1; j < n; j++)
                    if (matrix[i][j] == 0)
                        matrix[i][0] = matrix[0][j] = 0;
            }
            for (int i = m - 1; i >= 0; i--)
            {
                for (int j = 1; j < n; j++)
                    if (matrix[i][0] == 0 || matrix[0][j] == 0)
                        matrix[i][j] = 0;
                if (flagCol0) matrix[i][0] = 0;
            }
        }
    }
}
